package com.feishi.core.util.common.lecode;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
 * 实现 LRUCache 类：
 *
 * LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 *  
 *
 * */
public class LRU {

    public static void main(String[] args) {
        LRU lru=new LRU(3);
        lru.put(1,1);
        lru.put(2,2);
        lru.put(3,3);
        lru.put(4,4);
        System.out.println(lru.get(4));
        System.out.println(lru.get(3));
        System.out.println(lru.get(2));
        System.out.println(lru.get(1));
        lru.put(5,5);
        System.out.println(lru.get(1));
        System.out.println(lru.get(2));
        System.out.println(lru.get(3));
        System.out.println(lru.get(4));
        System.out.println(lru.get(5));
    }

    public LRU(int capacity) {
        this.capacity=capacity;
    }
    public Map<Integer,Node> map=new HashMap();
    private final int capacity;
    LinkedHashMap<Integer,Integer> linkedHashMap=new LinkedHashMap();
    public int get(int key) {
        Node node = getNode(key);
        if(node==null){
            return -1;
        }
        return node.value;
    }

    private Node getNode(int key) {
        Node node = map.get(key);
        if(node==null){
            return null;
        }

        addToEnd(node);
        return node;
    }

    private void addToEnd(Node node) {
        if(header==null){
            header=node;
            end=node;
            return;
        }
        if(node==header){
            if(node.next==null)return;
            node.next.pre=null;
            header=node.next;
            end.next=node;
            node.pre=end;
            node.next=null;
            end=node;
            return;
        }
        if(node==end){
            return;
        }
        if(node.pre!=null&&node.next!=null){
            node.pre.next=node.next;
            node.next.pre=node.pre;

            node.pre=end;
            end.next=node;
            node.next=null;
            end=node;
            return;
        }else {
            end.next=node;
            node.pre=end;
            end=node;
        }


    }

    public void put(int key, int value) {
        Node node=getNode(key);
        if(node==null){
            node=new Node(key,value);
            addToEnd(node);
            map.put(key,node);
            if(map.size()>capacity){
                map.remove(header.key,header);
                header=header.next;
                if(header==null){
                    System.out.println(111);
                }
                header.pre=null;
            }
            return;
        };
        node.value=value;

    }
    Node header;
    Node end;
    public class Node{
        Node pre;
        Node next;
        int value;
        int key;

        public Node(int key, int value) {
            this.key=key;
            this.value=value;
        }
    }

}
